//An ugly number is a positive integer whose prime factors are limited to 2, 3, 
//and 5. 
//
// Given an integer n, return the nth ugly number. 
//
// 
// Example 1: 
//
// 
//Input: n = 10
//Output: 12
//Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 
//ugly numbers.
// 
//
// Example 2: 
//
// 
//Input: n = 1
//Output: 1
//Explanation: 1 has no prime factors, therefore all of its prime factors are li
//mited to 2, 3, and 5.
// 
//
// 
// Constraints: 
//
// 
// 1 <= n <= 1690 
// 
// Related Topics 堆 数学 动态规划 
// 👍 658 👎 0


package leetcode.editor.cn;

import java.util.*;

//Java：Ugly Number II
class P264UglyNumberIi {
    public static void main(String[] args) {
        Solution solution = new P264UglyNumberIi().new Solution();
        solution.nthUglyNumber(10);
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int nthUglyNumber1(int index) {
            // 0-6的丑数分别为0-6
            if (index < 7) {
                return index;
            }
            //p2，p3，p5分别为三个队列的指针，newNum为从队列头选出来的最小数
            int p2 = 0, p3 = 0, p5 = 0, newNum = 1;
            List<Integer> arr = new ArrayList<>();
            arr.add(newNum);
            while (arr.size() < index) {
                //选出三个队列头最小的数
                newNum = Math.min(arr.get(p2) * 2, Math.min(arr.get(p3) * 3, arr.get(p5) * 5));
                //这三个if有可能进入一个或者多个，进入多个是三个队列头最小的数有多个的情况
                if (arr.get(p2) * 2 == newNum) {
                    p2++;
                }
                if (arr.get(p3) * 3 == newNum) {
                    p3++;
                }
                if (arr.get(p5) * 5 == newNum) {
                    p5++;
                }
                arr.add(newNum);
            }
            return newNum;
        }

        public int nthUglyNumber2(int n) {
            int[] factors = {2, 3, 5};
            PriorityQueue<Long> heap = new PriorityQueue<Long>();
            heap.offer(1L);
            int ugly = 0;
            for (int i = 0; i < n; i++) {
                long curr = heap.poll();
                ugly = (int) curr;
                for (int factor : factors) {
                    long next = curr * factor;
                    if (!heap.contains(next)) {
                        heap.offer(next);
                    }
                }
            }
            return ugly;
        }

        int nthUglyNumber(int n) {
            long count = 0;
            int num = 1;
            for (; ; ++num) {
                long i = num;
                while (i % 5 == 0) {
                    i /= 5;
                }
                while (i % 2 == 0) {
                    i /= 2;
                }
                while (i % 3 == 0) {
                    i /= 3;
                }
                if (i == 1) {
                    ++count;
                    if (count == n) {
                        return num;
                    }
                }
            }
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}